package leetcode;

/**
 * Created by Ghost on 2014/12/13.
 */
public class Find_Minimum_in_Rotated_Sorted_Array_II {
    public int findMin(int[] num) {
        if (num == null)
            return 0;
        if (num.length == 1)
            return num[0];
        int i = 0;
        for (i = num.length - 1; i >= 0 && num[i] == num[0]; i--) ;
        if (i == -1)
            return num[0];


        int start = 0, end = i, mid = 0;
        if (num[start] < num[end]) {
            return num[start];
        } else {
            while (start < end-1) {
                mid = (start + end) >> 1;
                if (num[start] == num[mid]) {
                    for (start = mid + 1; start < end && num[start] == num[mid]; start++) ;
                    start--;
                } else if (num[end] == num[mid]) {
                    for (end = mid - 1; end > start && num[end] == num[mid]; end--) ;
                    end++;
                } else {
                    if (num[mid] < num[start])
                        end = mid;
                    else
                        start = mid;
                }
            }
        }
        return num[end]>num[start]?num[start]:num[end];
    }

    public static void main(String[] args) {
        Find_Minimum_in_Rotated_Sorted_Array_II find_minimum_in_rotated_sorted_array_ii = new Find_Minimum_in_Rotated_Sorted_Array_II();
        int[] num = { 1,2,3,4,5};
        System.out.println(find_minimum_in_rotated_sorted_array_ii.findMin(num));
    }
}
